Préambule : nous avons commencé le TD par un rappel sur la récursivité et nous avons fait plusieurs exercices sur Pythontutor de sorte à ce que vous visualisiez la pile d'exécution et que vous compreniez bien comment sont effectués les appels récursifs et les instructions situées après un appel récursif dans le corps d'une méthode.
Attention, important : vous devez travailler par vous-mêmes et essayer de comprendre ce que font les algorithmes que vous lisez et que vous écrivez. N'hésitez pas à prendre un crayon et une feuille de brouillon pour dérouler, étape par étape, ce qui se passe dans l'ordinateur. N'hésitez pas non plus à refaire des simulations avec Python Tutor de sorte à mieux comprendre ce qui se passe lorsque vous déclenchez un appel récursif.
Exercice 1. Écrire un algorithme récursif qui permet de vérifier si une chaîne contient un caractère. Rappel : nous avons déjà écrit la solution de cet exercice en itératif.
In [1]:
%load_ext doctestmagic
In [2]:
def rechercheRecursive (chaine,carac,i):
'''
:entree: chaine (string)
:entree: caractère (string)
:entree: i (int)
:sortie: present (booleen)
:pre-conditions: i doit être fixé à 0 lors de l'appel, carac doit être un caractère seul, la chaîne peut être vide.
:post-condions: le booléen est fixé à vrai si la chaîne contient le caractère et à faux sinon (y compris dans le cas de la chaîne vide)
>>> rechercheRecursive("Bonjour", "j", 0)
True
>>> rechercheRecursive("Bonjour", "r", 0)
True
>>> rechercheRecursive("", "j", 0)
False
>>> rechercheRecursive("Bonjour", "a", 0)
False
'''
if i==len(chaine):
present=False
elif chaine[i]==carac:
present=True
else:
present=rechercheRecursive(chaine,carac,i+1)
return present
print(rechercheRecursive("bonjour",'a',0))
print(rechercheRecursive("bonjour",'j',0))
print(rechercheRecursive("",'j',0))
print(rechercheRecursive("bonjour",'r',0))
In [3]:
%doctest rechercheRecursive
La solution précédente est valide mais elle a l'inconvénient d'utiliser un indice en passage de paramètre, indice qui doit systématiquement être fixé à 0 lors de l'appel de la méthode. Une solution consisterait à "encapsuler" l'appel de cette méthode dans une autre méthode qui aurait une spécification plus simple, mais c'est un peu "trop facile". La solution ci-dessous est nettement plus élégante, même si elle a l'inconvénient de construire une nouvelle chaîne de caractères à chaque appel récursif.
In [4]:
def rechercheRecursiveBis(chaine,carac):
'''
:entree: chaine (string)
:entree: caractère (string)
:sortie: present (booleen)
:pre-conditions: carac doit être un caractère seul, la chaîne peut être vide.
:post-condions: le booléen est fixé à vrai si la chaîne contient le caractère et à faux sinon (y compris dans le cas de la chaîne vide)
>>> rechercheRecursiveBis("Bonjour", "j")
True
>>> rechercheRecursiveBis("Bonjour", "r")
True
>>> rechercheRecursiveBis("", "j")
False
>>> rechercheRecursiveBis("Bonjour", "a")
False
'''
if len(chaine)==0:
a=False
elif chaine[0]==carac:
a=True
else:
a=rechercheRecursiveBis(chaine[1:],carac)
return a
print(rechercheRecursiveBis("bonjour",'a'))
print(rechercheRecursiveBis("bonjour",'j'))
print(rechercheRecursiveBis("bonjour",'r'))
print(rechercheRecursiveBis("","r"))
Exercice 2. Écrire une méthode récursive pour calculer la somme des éléments d'une liste. Vous écrirez également le contrat.
In [5]:
def sommeRec(l):
'''
:entree l: une liste de nombres (entiers ou flottants)
:sortie somme: la somme des éléments de la liste
:pre-conditions: la liste peut être vide
:post-condition: somme contient la somme des éléments de la liste, et est donc du même type que les éléments.
>>> sommeRec([1, 2, 3])
6
>>> sommeRec([])
0
>>> sommeRec([6, 42.2, 34])
82.2
'''
somme=0
if len(l)>1:
somme=l[0]+sommeRec(l[1:])
elif len(l)==1:
somme+=l[0]
return somme
print(sommeRec([1, 2, 3]))
print(sommeRec([]))
print(sommeRec([6, 42.2, 34]))
%doctest sommeRec
Encore une fois, la solution ci-dessus est correcte mais elle est loin d'être "simple" et facile à lire pour quelqu'un d'autre que celui ou celle qui a écrit l'algorithme. On va donc (ci-dessous) proposer une ré-écriture plus simple.
In [6]:
def sommeRecBis(tab):
'''
:entree l: une liste de nombres (entiers ou flottants)
:sortie somme: la somme des éléments de la liste
:pre-conditions: la liste peut être vide
:post-condition: somme contient la somme des éléments de la liste, et est donc du même type que les éléments.
>>> sommeRecBis([1, 2, 3])
6
>>> sommeRecBis([])
0
>>> sommeRecBis([6, 42.2, 34])
82.2
'''
if len(tab) == 0:
somme = 0
else:
somme = tab[0]+sommeRecBis(tab[1:])
return somme
print(sommeRecBis([1, 2, 3]))
print(sommeRecBis([]))
print(sommeRecBis([6, 42.2, 34]))
%doctest sommeRecBis
Exerice 3. Écrire un algorithme qui permet de rechercher un nombre dans un tableau trié. Proposez une solution récursive et une solution non récursive.
In [7]:
def rechercheTab(tab,a):
'''
:entree tab: un tableau de nombres (entiers ou flottants) triés
:entree a: le nombre recherché
:sortie i: l'indice de la case du tableau dans laquelle se trouve le nombre.
:pré-conditions: le tableau est trié par ordre croissant de valeur.
:post-condition: l'indice de la première occurrence trouvée du nombre est renvoyé.
Si le nombre n'est pas présent dans le tableau, on retourne -1.
:Remarque : on appelle ce type de recherche "recherche par dichotomie".
>>> rechercheTab([0,1,2,3,4],1)
1
'''
i=-1
b=len(tab)//2
if tab[b]==a:
i=b
elif b == 0:
i = -1
elif tab[b]>a: # Si la valeur du milieu du tableau est plus grande que la valeur recherchée, on recherche dans la partie gauche du tableau
i=rechercheTab(tab[:b],a)
else: # Sinon, on recherche dans la partie droite et on gère le décalage des indices.
i=rechercheTab(tab[b:],a)
if i != -1:
i = i+b
return i
print(rechercheTab([0,1,2,3,4],1))
print(rechercheTab([0,1,2,3,4],5))
print(rechercheTab([0,1,2,3,4],4))
print(rechercheTab([0,1.3,2.7,3.4],0))
Devoirs à faire à la maison :